// https://leetcode-cn.com/problems/next-permutation/
// 31. 下一个排列
function nextPermutation(nums: number[]): void {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    if (i >= 0) {
        let j = nums.length - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        swap(nums, i, j);
    }

    reverse(nums, i + 1);

    function swap(nums: number[], i: number, j: number): void {
        const t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    function reverse(nums: number[], start: number): void {
        let left = start;
        let right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}
